1. Field
This disclosure relates to compression or encoding techniques in lossy networks, more particularly to building codebooks in lossy networks.
2. Background
Encoding data to compress it has several advantages, especially for communication networks. The reduction in the size of data needing to be sent reduces the bandwidth required to send it. This in turn avoids congestion on the network and allows the bandwidth that would otherwise be used to transmit the uncompressed data to be used for other transmissions.
In lossless networks, codebook or dictionary encoding can be very powerful. Examples include Lempel-Ziv (LZ) or Huffmann coding. Dictionary methods provide effective mechanisms for generic compression of data streams over a reliable channel. A reliable channel ensures no loss of data between a transmitter and a receiver. This is required because the receiver must also use the same data stream used to construct the dictionary in the transmitter. For example, in modem communication Lempel-Ziv based algorithms such as ITU (International Telecommunications Union) Recommendation V.44 and V.42 are used over a reliable link layer. The reliable link ensures that the compressor or encoder and the decompressor or decoder remain in sync.
These types of techniques are very desirable for lossy packet networks as well as lossless networks. However there are problems that arise with lossy packet networks, when a reliable transport cannot be considered. Full reliability can be achieved through acknowledgement and retransmit schemes, but the resulting delays or latency in the network is unbounded, making this unsuitable for some applications requiring low latency. An example may be ClearChannel applications over Internet Protocol (IP) networks. Forward Error Correction may be considered, but actually only reduces the resulting packet loss, and does not guarantee a reliable link.
Current techniques that allow dictionary compression in lossy packet networks include a notification scheme and a per-packet scheme. In the notification scheme, the receiving entity, or receiver, notifies the transmitter that a packet has been lost. The two entities reset their dictionaries and go through a synchronization process. This has a problem with loss of data between the loss of the first packet and the re-synchronization, as packets that are received between those two events have to be discarded. Additionally, after the loss of the packet and the re-synchronization, during which the dictionaries are reset, both entities must build up their compression codebooks, resulting in an even longer period for which there is less than optimal compression.
In per-packet schemes, the encoder and decoder can build their dictionaries on a per packet basis. At the beginning of each packet, the dictionaries at either end are reset. This solves the problem of synchronizing the dictionaries. However, a single packet is typically too small an amount of data to allow sufficient dictionary training for good compression. In addition, rebuilding a dictionary every packet increases the operating overhead of the sending and receiving entities, which may prove unacceptable.